#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	initbuffer();
	// NOTE: this function is called before any other function as this fills in information
	pf.read(pid, this->buffer); // pf reads pid from argument into the current BTLeafNode's buffer
	// we also want to read in endPid() so we know if there is still a next node pointer
	// currnode = pid; // stores current node we are in (might not be needed)
	// eofnode = pf.endPid(); // stores the last Pid + 1 (might not be needed)
	
	ecount = buffer[0];
	nxtndeptr = buffer[1];
	maxentrynum = 82; // set the maximum number of entry
	root_pid = buffer[4]; // root's pid
    height_of_tree = buffer[5]; // tree height
    node_type = buffer[7]; // 0 for non-leaf and root, 1 for leafnode
    hasnext = buffer[8]; 
    // node_type has to be 1 here

	buftovec(); // places buffer into vector
	// std::sort(keyrid.begin(), keyrid.end(), mysorter);
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	/* NOTE: vector will have the most up-to-date changes
	 but we only pass info to the write through the buffer so 
	 we need to make the data in vector back into int buffer form */
	
	sortVector(); // sorts out vector 
	// we have to sort before transfering vector to buffer
	vectobuf(); // transfer back vector to buffer
	// because we are writing buffer to pageid in the next step
	pf.write(pid, this->buffer); // writes into the pid in pf, our buffer from read after modification
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	// ecount stores the # of valid entries, every entry has a key
	return ecount; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	/* NOTE: we can insert as much as we want here 
	sorting does not happen during insert, 
	only happens when we write back to pagefile */
	
	// not sure if we need to check that key is not negative and does not already exist
	
	// note that we could have put sorting here but we thought it was
	// not efficient since we don't want to sort everytime we insert a new value
	if(ecount==maxentrynum){
		// then we should not be using insert function but insertandsplit
		return RC_NODE_FULL; 
	}
	keyandrid kr;
	kr.key = key;
	kr.recid.pid = rid.pid;
	kr.recid.sid = rid.sid;
	
	keyrid.push_back(kr); // pushed into vector but unsorted
	ecount++; // increment the number of entries
	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	/* NOTE: Inside the insertAndSplit function, you do not need to know the pageid
	 pointing to the sibling node. You can assume the function that calls insertAndSplit() 
	 knows the pageid for the sibling node, and calls setNextNodePtr() to set 
	 that pageid. */

	// we assume this function is only called when the node is already full
	// we will need to sort at this step to ensure the new node is sorted
	
	// 1. insert into vector
	// 2. sort vector
	// 3. split into 2 int buffers
	keyandrid kr;
	kr.key = key;
	kr.recid.pid = rid.pid;
	kr.recid.sid = rid.sid;
	
	keyrid.push_back(kr); // pushed into vector but unsorted
	ecount++; // increment the number of entries

	sortVector(); 

	int has_next_or_not = hasnext;
	// now we want to split 82 + 1 overflow entry = 83 entries
	// 2 leafnodes of 41 and 42 entries each
	// [0-40] & [41-84] = 0-82 meaning 83 entries

	// [0-40] in our current node
	setvalues(41, 82, root_pid, height_of_tree, 1, 1); // sets buffer information, 43 entries, 84 max
	int count = 10; 
	// start loop to put vector into buffer
	for(int i = 0; i<ecount; i++){
		buffer[count] = keyrid[i].key;
		buffer[count+1] = keyrid[i].recid.pid;
		buffer[count+2] = keyrid[i].recid.sid;
		count += 3;
	}

	// [43-84] in next node
	siblingKey = keyrid[43].key; // sets siblingkey to the first value in the second node
	sibling.setNextNodePtr(nxtndeptr); // sets the new node's next ptr
	// old node (43entries) --points--> new node (42 entries) --points--> next node 
	sibling.setvalues(42, 82, root_pid, height_of_tree, 1, has_next_or_not);

	int limit = 83; // limit = 41 + 42 = 83

	int counter = 10;
	for(int i = 43; i<limit; i++){
		sibling.buffer[counter] = keyrid[i].key;
		sibling.buffer[counter+1] = keyrid[i].recid.pid;
		sibling.buffer[counter+2] = keyrid[i].recid.sid;
		counter += 3;
	}

	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	// go through the vector for the searchkey and store into eid 
	// the value equal to or greater than searchkey
	for(int i = 0; i < ecount; i++){
		// key equal to searchKey
		if(keyrid[i].key == searchKey){
			eid = i;
			return 0;
		}
		
		// key greater than searchKey (this means we are already over the estimated position)
		if(keyrid[i].key > searchKey){
			eid = i;
			return 0;
		}
 	}
	return RC_NO_SUCH_RECORD; // happens if the locate ends without finding a value equal or greater than searchKey
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	// need to call locate from inside here
	// read key and rid from eid
	if(eid >= ecount){
		// if eid >= ecount, then no record of such exists
		// eg. ecount = 10, eid = 10, keyrid goes from keyrid[0] to keyrid[9]
		// eid where keyrid[10] does not exist
		return RC_NO_SUCH_RECORD;
	}
	key = keyrid[eid].key;
	rid.pid = keyrid[eid].recid.pid;
	rid.sid = keyrid[eid].recid.sid;
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	return buffer[1];
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	
	//if(pid!=(currnode+1)){
		// assuming we want our pageids to be sequential
		// then we should give an error otherwise
	//	return RC_INVALID_PID;
	//}
	// set the last slot in int buffer to the pid
	buffer[1] = pid;
	
	// store this info inside a special variable, nxtndeptr
	nxtndeptr = pid; 
	return 0; 
}

// ===================user made functions=========================
// initializes buffer to 0
// unused atm since int buffer comes from the read function memcpy
void BTLeafNode::initbuffer()
{
	int psize = (PageFile::PAGE_SIZE)/4; // should give 256
	for(int i = 0; i<psize; i++){
		buffer[i] = -1;
	}
}

// parses the buffer into vector
void BTLeafNode::buftovec()
{
	// recall that the 1st 4 values are not part of the (key, rid) pair
	for(int i = 4; i<ecount; i++){
		int mykey = buffer[i];
		PageId mypid = buffer[i+1];
		int mysid =  buffer[i+2];
		
		keyandrid kr;
		kr.key = mykey;
		kr.recid.pid = mypid;
		kr.recid.sid = mysid;
		
		keyrid.push_back(kr); // add keyandrid entry to vector keyrid
	
		i += 2;
	}
	ecount = keyrid.size(); // stores the # of elements in the vector into ecount, 
}

// parses vector to buffer
void BTLeafNode::vectobuf()
{
	// recall that the 1st 4 values in the int buffer are characteristics of the pagefile
	// and not actual data yet
	
	// initbuffer(); // we first initialize buffer to be all 0s
	buffer[0] = ecount; // current number of entries
	buffer[1] = nxtndeptr; 
	// buffer[2] = curr_pid; 
	buffer[3] = maxentrynum; // 256 - 4 (headers) = int buffer[252], meaning 252/3 = 84 entries
	buffer[4] = root_pid;
	buffer[5] = height_of_tree;
	buffer[6] = node_type;
	buffer[7] = hasnext;
	buffer[8] = buffer[9] = -1;

	int count = 10;
	// start loop to put vector into buffer
	for(int i = 0; i<ecount; i++){
		buffer[count] = keyrid[i].key;
		buffer[count+1] = keyrid[i].recid.pid;
		buffer[count+2] = keyrid[i].recid.sid;
		count += 3;
	}
}

void BTLeafNode::setecount(int ec)
{
	ecount = ec;
}

void BTLeafNode::setmaxentrynum(int mxn)
{
	maxentrynum = mxn;
}

//this is the sorting
void BTLeafNode::sortVector() {
	sorting mySort;
	//using object as comparison
	sort(keyrid.begin(), keyrid.end(), mySort);
}

void BTLeafNode::setvalues(int ec, /*PageId curpid,*/ int m_ent_num, PageId rpid, int hoft, int type, int next){
	ecount = buffer[0] = ec;
	// buffer[1] is set using setnextnodeptr() function
	// curr_pid = buffer[2] = curpid;
	maxentrynum = buffer[3] = m_ent_num;
	root_pid = buffer[4] = rpid;
	height_of_tree = buffer[5] = hoft;
	node_type = buffer[6] = type;
	hasnext = buffer[7] = next;
}

void BTLeafNode::incr_heightoftree(){
	buffer[5] += 1;
	height_of_tree += 1;
}

int BTLeafNode::gethasnext(){
	return hasnext; 
}
/*bool BTLeafNode::ridandkeySort(const ridandkey & d1, const ridandkey & d2)
{
	return d1.key < d2.key;
}*/

// ===============end user made functions=========================

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	int retval = pf.read(pid, this->buffer);
	keycount = buffer[0];
	pidcount = buffer[1];
	maxkeycount = buffer[2];
	maxpidcount = buffer[3];
	spaceused = buffer[4];
	node_type = buffer[6];
	return retval;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	buffer[0] = keycount;
	buffer[1] = pidcount;
	buffer[2] = maxkeycount;
	buffer[3] = maxpidcount;
	buffer[4] = spaceused;
	buffer[6] = node_type;
	int retval = pf.write(pid, this->buffer);
	return retval; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ return keycount; }


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	/* NOTE: this function is called from the outside by user with 
	information regarding leafnodes and has already made appropriate 
	changes to the other spaces in leaf node */

	/* NOTE: have to make sure (from higher level function callers)
	that such examples as below do not happen...

	pid1 = (0,5,7,9)
	key1 = 10
	pid3 = (10, 20, 25)
	key3 = 30
	pid4 = (30, 35, 50)

	want to insert:
	pid2 = (11, 16) 
	key2 = 20

	incorrect result...
	(0,5,7,9) 10 (11,16) 20 (10,20,25) 30 (30,35,50)
	correct result...
	(0,5,7,9) 10 (10, 11,16) 20 (20,25) 30 (30,35,50) */

	if(256<(spaceused+2)){
		// node will go over space limit
		return RC_NODE_FULL;
	}
	for(int i = 8; i<spaceused; i+=2){
		// go over keys one by one
		// possible cases for insertion:

		/* case 1: insert happens right at the start where the key 
		is immediately bigger than the key to be inserted
		key being read = buffer[6] */

		if((buffer[i]>key)&&(i==8)){
			insertKeyPid(key, pid, i);
			spaceused += 2;
			return 0;
		}

		/* case 2: right at the end where key to be inserted is actually
		the largest value 
		key being read = last filled key buffer */


		if((buffer[i]<key)&&(i==(spaceused-2))){
			buffer[i+3] = key;
			buffer[i+4] = pid; 
			spaceused += 2;
			keycount++;
			pidcount++;
			return 0;
		}

		/* case 3: somewhere in the middle where we do a normal insert
		key being read = anything other than the 2 previous ones */

		if((buffer[i]<key)&&(buffer[i+2]>key)){
			int entryspace = i+2;
			insertKeyPid(key, pid, entryspace);
			spaceused += 2;
			return 0;
		}
	} 
	return -1; // error, no insert done...  
	/* the last return statement should almost never get called because 
	at the worst case, the insert will happen at the end of the buffer
	OR at the beginning */ 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	/* NOTE: this function will be called by higher level
	only when the keys and pid inserted is already calculated 
	to overflow the current non-leaf node. */

	buf_to_tmpbuf(); // put buffer to tmpbuffer which has more space

	for(int i = 8; i<spaceused; i+=2){

		if((buffer[i]>key)&&(i==8)){
			insertKeyPid_tmp(key, pid, i);
			spaceused += 2;
			return 0;
		}

		if((buffer[i]<key)&&(i==(spaceused-2))){
			tmpbuffer[i+3] = key;
			tmpbuffer[i+4] = pid; 
			spaceused += 2;
			keycount++;
			pidcount++;
			return 0;
		}

		if((buffer[i]<key)&&(buffer[i+2]>key)){
			int entryspace = i+2;
			insertKeyPid_tmp(key, pid, entryspace);
			spaceused += 2;
			return 0;
		}
	} 
	// at this point, we have a fully inserted tmpbuffer
	// ready for splitting

	// 256 possible spaces, 258 spaces used in tmpbuffer
	// first 5 buffer[0-6] filled with buffer information
	// [7-257] actual pageid, key information

	// 7, 9, 11, ... 257 pageid entry number
	// 8, 10, 12, ... 256 key entry number
	// 258 slots - 7 to hold buffer info = 251 = keys + pageids
	// 1 slot out of 251 is the midkey so 250 left
	// 250/2 = 125
	// first buffer will use 125 of it's spaces
	// 62 for keys, 63 for pids
	// second buffer will use 125 of it's spaces
	// 62 for keys, 63 for pids

	// our first buffer will have
	// buffer[0] = 62
	// buffer[1] = 63
	// buffer[2] = 124 
	// buffer[3] = 125
	// buffer[4] = 125
	// 7+125=132
	for(int i = 7; i < 132; i++){
		buffer[i] = tmpbuffer[i];
	}

	// buffer[132] = 133th entry is the midkey entry
	midKey = tmpbuffer[132];

	// our overflow buffer will have
	// buffer[0] = 62
	// buffer[1] = 63
	// buffer[2] = 124 
	// buffer[3] = 125
	// buffer[4] = 125

	for(int i = 7; i < 125; i++){
		sibling.buffer[i] = tmpbuffer[i+126];
	}

	// last step: set the information
	setvalues(62,63,124,125,125,0);
	sibling.setvalues(62,63,124,125,125,0);
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	// check keys sequentially inside non-leaf node
	for(int i = 8; i<spaceused; i++){
		if(buffer[i]==searchKey){
			// if key = searchkey, pid = pid after key
			pid = buffer[i+1];
			return 0;
		}
		if(buffer[i]>searchKey){
			// if key > searchkey, pid = pid before key
			pid = buffer[i-1];
			return 0;
		}
		i++; // since we are going 2 by 2 spaces
	}
	pid = (spaceused-1); // if we get to this point, then searchkey is in last pid
	return 0; // this is when all the keys in buffer have been exhausted 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	/* NOTE: this function is called without reading anything.
	this will most probably be the first non-leaf node to be called. 
	As such, the information inside must be initialized to the
	attributes of a root. */

	/* buffer[0] = keycount = 1;
	buffer[1] = pidcount = 2;
	buffer[2] = maxkeycount = 124; 
	buffer[3] = maxpidcount = 125;
	buffer[4] = spaceused = 10; */
	setvalues(1, 2, 124, 125, 10, 0);
	buffer[7] = pid1;
	buffer[8] = key;
	buffer[9] = pid2;
	return 0; 
}

// ============= begin user function ==================
void BTNonLeafNode::insertKeyPid(int key, PageId pid, int index) {
	
	//store the prev key and prevPage id to replace the next index(incremental by 2)
	int prevKey = buffer[index];
	PageId prevPageId = buffer[index+1];
	
	for(int i = index+2; i < spaceused; i+=2) {
		//store the current key because it will be replaced by the prev
		int tempKey = buffer[i];
		PageId tempPageId = buffer[i+1];
		
		//replace the current index with the prev
		buffer[i] = prevKey;
		buffer[i+1] = prevPageId;
		
		//set prev key to the temp
		prevKey = tempKey;
		prevPageId = prevPageId;
	}
	//store the new insert
	buffer[index] = key;
	buffer[index+1] = pid;
	keycount++;
	pidcount++;	
}

// function below inserts new value into tmp buffer
void BTNonLeafNode::insertKeyPid_tmp(int key, PageId pid, int index) {
	
	// store the prev key and prevPage id to replace the next index(incremental by 2)
	// buf_to_tmpbuf();

	int prevKey = tmpbuffer[index];
	PageId prevPageId = tmpbuffer[index+1];
	
	int tmpbufkc = spaceused+2; // tmpbuffer keycount + 2 (for new value)
	for(int i = index+2; i < tmpbufkc; i+=2) {
		//store the current key because it will be replaced by the prev
		int tempKey = tmpbuffer[i];
		PageId tempPageId = tmpbuffer[i+1];
		
		//replace the current index with the prev
		tmpbuffer[i] = prevKey;
		tmpbuffer[i+1] = prevPageId;
		
		//set prev key to the temp
		prevKey = tempKey;
		prevPageId = prevPageId;
	}
	//store the new insert
	tmpbuffer[index] = key;
	tmpbuffer[index+1] = pid;
}

// passes values in buffer to tmp buffer
void BTNonLeafNode::buf_to_tmpbuf(){
	for(int i = 0; i < spaceused; i++){
		buffer[i] = tmpbuffer[i];
	}
	// last 2 values of tmpbuffer will be junk 
}

void BTNonLeafNode::setvalues(int kc, int pc, int mkc, int mpc, int s_used, int type){
	keycount = buffer[0] = kc;
	pidcount = buffer[1] = pc;
	maxkeycount = buffer[2] = mkc;
	maxpidcount = buffer[3] = mpc;
	spaceused = buffer[4] = s_used;
	node_type = buffer[6] = type;
}
// ============== end user function ===================
